When a figure is drawn using a graphic system, a figure to be drawn is generally divided into a group of triangles, and pixels configuring the figure are painted. FIG. 1 is an explanatory view of a result of drawing in the above-mentioned drawing system. In FIG. 1, a substantially square figure is divided into two figures, that is, an upper left triangle and a lower right triangle. First, the pixels configuring the upper left triangle, that is, the preceding triangle, are painted, and then the pixels configuring the lower right triangle, that is, the subsequent triangle, are painted. However, in this case, the side as the boundary of the two triangles is shared. That is, the pixels configuring the side are double painted. For example, when a semitransparent figure is drawn, the color of the side is unfortunately deep.
FIG. 2 is an explanatory view of a common conventional system for preventing the above-mentioned problem. Generally, in the first conventional system, the rightmost side and the lowermost side of a triangle (in this example, referred to as end sides) are not painted, that is, paint prohibited, thereby preventing the double painting. Namely, in FIG. 2, the pixels configuring the rightmost side of the preceding triangle, that is, the side of the boundary of the two triangles, are painted when the preceding triangle is drawn, that is, the drawing is prohibited. The side can be protected against the double painting by painting the side when the subsequent triangle is drawn. However, in the system illustrated in FIG. 2, the drawing of the rightmost side and the lowermost side is inhibited, and the end sides are not painted, thereby generating an image not matching the image to be drawn.
FIG. 3 is an explanatory view of the second prior art of the system of inhibiting double painting of a shared side. In this conventional system, the contour line of each triangle is traced after drawing each triangle in the system illustrated in FIG. 2, thereby solving especially the problem of not painting the rightmost side and the lowermost side. That is, after drawing the preceding triangle, the contour line of the triangle is traced by lines including the draw inhibit pixels, and the pixels of the rightmost side and the lowermost side are traced by the contour line after drawing the subsequent triangle, thereby correctly drawing a figure to be drawn.
However, since the contour line is partially double painted in this method, the method cannot be applied to a semitransparent figure, and it is necessary to fine-tune the position of the vertex of contour lines by drawing a bold contour line to avoid the space made between a triangle and an contour line by different algorithms between drawing the triangle and drawing the line, arithmetic errors, etc. There is also the problem that tracing a contour line after drawing a triangle reduces the efficiency in accessing memory storing drawing data, and degrades the performance.
FIGS. 4 through 9 are explanatory views of the problems with the first conventional system illustrated in FIG. 2, that is, the system of not painting the rightmost side and the lowermost side, used when drawing an arbitrary closed polygon including a concave portion.
There are two common methods of drawing the above-mentioned closed polygons. The first method is to draw a figure by dividing a figure into a number of triangles not overlap one another while recursively retrieving coordinates of all vertexes configuring a closed polygon. However, it is hard to realize this method by hardware, and the method cannot be applied to a system of drawing a figure using a graphics LSI.
The second method is to receive the vertexes configuring a closed polygon as streaming data (the processes of the system is performed without knowing the final figure to be drawn), sequentially generate a triangle using input vertexes, and sequentially draw the triangle. Until a final triangle is drawn, the data of a result of drawing in progress is stored in a stencil buffer, and mapped with color information in a frame buffer after drawing a final triangle. When data is stored in a stencil buffer, an exclusive logical sum operation is performed between the data of the pixels drawn and stored in the stencil buffer and the data of the pixels configuring the triangle to be drawn, and the result is written back to the stencil buffer. This method is generally used in a graphics LSI.
FIG. 4 illustrates the shape of a closed polygon to be finally drawn. In accordance with the shape, the graphics system is provided with streaming vertex data in the order of V1, V2, V3, V4, V5, and V6 starting with the vertex V0. The black (square) portion refers to painted pixels and the white (square) portion refers to unpainted pixels.
FIG. 5 illustrates a drawing state of a triangle configured by three vertexes V0, V1, and V2 input first. The pixels of the rightmost sides, that is, the sides V0-V1 and V1-V2 are not painted. The bold solid line refers to a painted contour, and the bold broken line refers to an unpainted (erased) contour.
FIG. 6 illustrates the state in step 2 in which a triangle having three vertexes V0, V2, and V3 is drawn using the data of the next input vertex V3. In FIG. 6, in the portion overlapping the triangle drawn in step 1, the pixel data is “0” by the above-mentioned exclusive logical sum operation for erasure by painting. The pixel on the side V0-V2 of the triangle is also erased by the exclusive logical sum operation.
FIG. 7 illustrates the state in which the triangle V0-V3-V4 is drawn using the data of the vertex V4 input next. That is, in step 3, a triangle is configured using the first vertex V0 in the vertex data input as a stream, the vertex V4 input latest, and the vertex 3 input immediately before the vertex V4. In FIG. 7, the data for a number of pixels in the pixels of the newly drawn triangle is set to “0” by the exclusive logical sum operation, thereby entering the erased state.
FIG. 8 illustrates the state in which the triangle V0-V4-V5 is drawn using the next input data of the vertex V5. In the shapes drawn in FIG. 7, the pixels configuring the triangle whose lower side is painted are erased.
FIG. 9 illustrates the state in which the triangle V0-V5-V6 is drawn after finally inputting the data of the vertex V6. In the final drawing state, as compared with FIG. 4 illustrating the final state of the figure to be drawn, the sides V3-V4, V4-V5, and V0-V6 are erased in the contour of the closed polygon.
The problems with the prior art are described above in detail, but the conventional technology relating to the figure drawing system can be the patent documents 1 through 3, and the non-patent document 1. The patent document 1 discloses the perimeter line drawing data control system capable of simplifying the process of perimeter line data of a triangle by receiving the vertex coordinates as the data of the divisional triangles and an identification flag indicating a boundary line or a division line when a polygon is drawn by dividing it into a plurality of triangles, processing the perimeter line of each triangle on the basis of the identification flag, and drawing a figure.
The patent document 2 discloses a polygon dividing and drawing method and device capable of speeding up the drawing process and simplifying the system by simultaneously drawing a perimeter line when a divisional triangle is drawn by outputting in a simple control system the vertex information of a plurality of triangles generated by dividing a polygon.
The patent document 3 discloses a drawing device for realizing a painting process and a clipping process by a hardware configuration by providing in parallel a counter circuit for counting the number of clip vectors in each direction, a counter circuit for counting the number of draw vector in each direction, and a determining circuit for determining whether the coordinates refer to a starting point or an ending point in the painting region.
However, in the above-mentioned conventional technology, the problem that an end side cannot be painted by avoiding painting the pixels of the rightmost side and the lowermost side of divisional triangles, or the problem that the contour line of a figure is over-erased when an arbitrary closed polygon including a concave portion is drawn cannot be solved.
The non-patent document 1 describes drawing only once the perimeter and the vertex of a polygon and preventing double drawing, but the description of the method is simple, and it is hard to apply the method to preventing a contour line from being over-erased.                Patent Document 1: Japanese Laid-open Patent Publication No. 7-105390 “Perimeter Line Drawing Data Control System”        Patent Document 2: Japanese Laid-open Patent Publication No. 7-160899 “Polygon Dividing And Drawing Method And Device”        Patent Document 3: Japanese Laid-open Patent Publication No. 2002-208017 “Drawing Device”        Non-patent Document 1: “Open GL Programming Guide Version 2”, Open GL Developing Committee, translated by Koichi Matsuda, (KK) Pearson Education (December 2006)        